package com.jwetherell.my.problems.backtracking;


public class StringPermutation {

	public static void main(String[] args) {
		char [] chars = new char[] {'a','b','c'};
//		permute(chars, 0);
		printAllPermutations(chars, -1);
	}
	
//	private static void permute(char[] chars, int posNextToFixed) {
//		if (posNextToFixed == chars.length - 1) {
//			output(chars);
//			return;
//		}
//		
//		for (int j = posNextToFixed; j < chars.length; j++) {
//			swap(chars, posNextToFixed, j);
//			permute(chars, posNextToFixed + 1);
//			swap(chars, posNextToFixed, j);
//		}
//	}

	private static void swap(char[] chars, int posNextToFixed, int j) {
		char temp = chars[posNextToFixed];
		chars[posNextToFixed] = chars[j];
		chars[j] = temp;
	}

	private static void printAllPermutations(char[] chars, int posNextToFixed) {
//		if (reject(chars))
//			return;
//		
//		if (accept(chars))
		
		output(chars);
		posNextToFixed++;
		int replace = posNextToFixed + 1;
		
		char [] s = child(chars, posNextToFixed);
		while (s != null) {
			replace++;
			
			char [] newData = new char[s.length];
			for (int i = 0; i < s.length; i++) {
				newData [i] = s[i];
			}
			
			printAllPermutations(newData, posNextToFixed);
			s = sibling(s, posNextToFixed, replace);
		}
		
	}

	private static char[] sibling(char[] chars, int posNextToFixed, int replace) {
		
		if (replace == chars.length)
			return null;
		
		char [] newData = new char[chars.length];
		for (int i = 0; i < chars.length; i++) {
			newData [i] = chars[i];
		}
		
		char temp = newData [posNextToFixed];
		newData[posNextToFixed] = newData[replace];
		newData[replace] = temp;
		
		return newData;
	}

	private static char[] child(char[] parentData, int posNextToFixed) {
		if (posNextToFixed == (parentData.length - 1))
			return null;
		
		char [] newData = new char[parentData.length];
		for (int i = 0; i < parentData.length; i++) {
			newData [i] = parentData[i];
		}
		
		char temp = newData [posNextToFixed];
		newData[posNextToFixed] = newData[posNextToFixed + 1];
		newData[posNextToFixed + 1] = temp;
		
		return newData;
	}

	private static void output(char[] chars) {
		for (int i = 0; i < chars.length; i++)
			System.out.print(chars[i]);
		System.out.print("\n");
	}
	
}
